class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int begin = 0, end = nums.size() - 1;
        sort(nums.begin(), nums.end());
        while (begin <= end) {
            int mid = (begin + end) / 2;
            if (nums[mid] == mid + 1) {
                begin = mid + 1;
            }
            else if (nums[mid] > mid + 1) {
                begin = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }
        return nums[mid];
    }
};
